package Array;

import java.util.*;

/*
 * 输入一个数组中两个数相加等于target的下标
 * 因为返回的是两个数所在数组的位置，而且不重复，所以可以用map的数据结构
 */
public class Two_Sum {
	 public int[] twoSum(int[] nums, int target) {
	        int[] a=new int[2];
	        
	        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
	        for(int i=0;i<nums.length;i++) {
	            Integer n= map.get(nums[i]);
	            if(n==null) {
	                map.put(nums[i],i);
	            }
	             n=map.get(target-nums[i]);
	             if(n!=null && n<i) {
	                 a=new int[]{i,n};
	             }
	        }
	        
	        return a;
	    }
	 //如果用数组就需要双重遍历 ，时间复杂度高
	 //用hashmap存储，values存储位置，返回values就是位置。
}
